package solution.string;

/**
 * 
 * @author <a href="www.sureinterview.com">SureInterview</a>
 */
public class WildcardMatching {
	boolean mtch[][];

	boolean mtch2[];

	/**
	 * check if patt matches the string str.
	 * 
	 * @param str
	 *            the string to match
	 * @param patt
	 *            the pattern matching str. '*' is for 0 or more characters and
	 *            '.' is for exactly one character.
	 * @return true, if the pattern matches the string. otherwise, false.
	 */
	public boolean match(String str, String patt) {
		if (str == null || patt == null)
			return false;
		// convert them to arrays
		char[] cstr = str.toCharArray();
		char[] cpatt = patt.toCharArray();

		// create a boolean array of [0..len(cstr)][0..len(cpatt)]
		// initialize the elements of mtch[0][*] and mtch[*][0] to false
		// mtch[0][0] is true
		mtch = new boolean[cstr.length + 1][];
		for (int i = 0; i <= cstr.length; i++) {
			mtch[i] = new boolean[cpatt.length + 1];
		}
		mtch[0][0] = true;
		// update the '*' in the pattern because they matches 0-length
		// character.
		for (int i = 0; i < cpatt.length && cpatt[i] == '*'; i++) {
			mtch[0][i + 1] = true;
		}

		// check if the pattern cstr matches the string cstr
		for (int i = 0; i < cstr.length; i++) {
			boolean matched = false;
			for (int j = 0; j < cpatt.length; j++) {
				if (cpatt[j] == '.') {
					// the previous matching status (i,j) determine current
					// status (i+1,j+1)
					mtch[i + 1][j + 1] = mtch[i][j];
				} else if (cpatt[j] == '*') {
					// the previous matching status (i,*) determine current
					// status (i+1,j+1)
					mtch[i + 1][j + 1] = mtch[i][j] || mtch[i][j + 1]
							|| mtch[i + 1][j];
				} else {
					// the current status (i+1,j+1) is determined by current
					// character match and previous match
					mtch[i + 1][j + 1] = (cstr[i] == cpatt[j]) && mtch[i][j];
				}
				matched |= mtch[i + 1][j + 1];
			}
			if (!matched)
				return false;
		}

		return mtch[cstr.length][cpatt.length];
	}

	/**
	 * check if patt matches the string str. Same as {@link match} but
	 * one-dimension array is used.
	 * 
	 * @param str
	 *            the string to match
	 * @param patt
	 *            the pattern matching str. '*' is for 0 or more characters and
	 *            '.' is for exactly one character.
	 * @return true, if the pattern matches the string. otherwise, false.
	 */
	public boolean match2(String str, String patt) {
		if (str == null || patt == null)
			return false;
		// convert them to arrays
		char[] cstr = str.toCharArray();
		char[] cpatt = patt.toCharArray();

		// create a boolean array of [0..len(cpatt)]
		// initialize the elements of mtch[*] to false
		// mtch[0] is true
		mtch2 = new boolean[cpatt.length + 1];
		mtch2[0] = true;
		for (int i = 0; i < cpatt.length && cpatt[i] == '*'; i++) {
			mtch2[i + 1] = true;
		}

		// check if the pattern cstr matches the string cstr
		for (char element : cstr) {
			boolean matched = false;
			// calculate from right to left to preserve the previous status.
			for (int j = cpatt.length - 1; j >= 0; j--) {
				if (cpatt[j] == '*') {
					mtch2[j + 1] = mtch2[j] || mtch2[j + 1];
				} else {
					mtch2[j + 1] = ((cpatt[j] == element) || (cpatt[j] == '.'))
							&& mtch2[j];

					// if current character matches, update the following '*' in
					// patter because they can match a 0-length char.
					if (mtch2[j + 1]) {
						for (int k = j + 1; (k < cpatt.length)
								&& cpatt[k] == '*'; k++) {
							mtch2[k + 1] = true;
						}
					}
				}
				matched |= mtch2[j + 1];
			}
			if (!matched)
				return false;
			mtch2[0] = false;
		}

		return mtch2[cpatt.length];
	}
}
